ABSTRACT
Debugging multithreaded programs, which involves detection and identification of the cause of data races, has proved to be a hard problem. Although there has been significant amount of research on this topic, prior works rely on one important assumption - the debuggers must be aware of all the synchronization operations that take place during a program run. This assumption is a significant limitation as multithreaded programs, including the popular SPLASH-2 benchmark, have barriers and flag synchronizations implemented in the user code. We show that the lack of knowledge of these synchronization operations leads to unnecessary reporting of numerous races. Our experiments with SPLASH-2 benchmark suite show that 12-131 distinct segments in source code, on an average, give rise to well over 4 million dynamic instances of falsely reported races for these programs. We propose a dynamic software technique that identifies the user defined synchronizations exercised during a program run. This information not only helps avoids reporting of unnecessary races, but also helps a record/replay system to speedup the replay.
Our evaluation confirms that our synchronization detector is highly accurate with no false negatives and very few false positives. Thus, reporting of nearly all unnecessary races is avoided. Finally, we show that the knowledge of synchronization operations resulted in about 23% reduction in replay time.
- S.V. Adve, M.D. Hill, B.P. Miller, and R.H.B. Netzer. Detecting data races on weak memory systems. In Proceedings of the 18th International Symposium on Computer Architecture (ISCA), volume 19, pages 234--243, New York, NY, 1991. Google ScholarDigital Library
- E. Artiaga, N. Navarro, X. Martorell, Y. Becerra, M. Gil, and A. Serra. Experiences on the implementation of parmacs macros using different multiprocessor operating system interfaces.Google Scholar
- D.F. Bacon and S.C. Goldstein. Hardware-assisted replay of multiprocessor programs. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 194--206, New York, NY, USA, 1991. ACM Press. Google ScholarDigital Library
- S. Bhansali, W.-K. Chen, S. de Jong, A. Edwards, R. Murray, M. Drinić, D. Mihocka, and J. Chau. Framework for instruction-level tracing and analysis of program executions. In VEE '06: Proceedings of the 2nd international conference on Virtual execution environments, pages 154--163, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: preventing data races and deadlocks. In OOPSLA '02: Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 211--230, New York, NY, USA, 2002. Google ScholarDigital Library
- J.-D. Choi, B.P. Miller, and R.H.B. Netzer. Techniques for debugging parallel programs with flowback analysis. ACM Trans. Program. Lang. Syst., 13(4):491--530, 1991. Google ScholarDigital Library
- M. Christiaens and K. D. Bosschere. Trade, a topological approach to on-the-fly race detection in java programs. In JVM'01: Proceedings of the Java™ Virtual Machine Research and Technology Symposium on Java™ Virtual Machine Research and Technology Symposium, pages 15--15, Berkeley, CA, USA, 2001. USENIX Association. Google ScholarDigital Library
- A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 85--96, New York, NY, USA, 1991. ACM Press. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. Type-based race detection for Java. ACM SIGPLAN Notices, 35(5):219--232, 2000. Google ScholarDigital Library
- C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. SIGPLAN Not., 39(1):256--267, 2004. Google ScholarDigital Library
- R. Gupta. The fuzzy barrier: a mechanism for high speed synchronization of processors. In ASPLOS-III: Proceedings of the third international conference on Architectural support for programming languages and operating systems, pages 54--63, New York, NY, USA, 1989. ACM Press. Google ScholarDigital Library
- B. Krena, Z. Letko, R. Tzoref, S. Ur, and T. Vojnar. Healing data races on-the-fly. In PADTAD '07: Proceedings of the 2007 ACM workshop on Parallel and distributed systems: testing and debugging, pages 54--64, New York, NY, USA, 2007. ACM Press. Google ScholarDigital Library
- L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, 1978. Google ScholarDigital Library
- C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. SIGPLAN Not., 40(6):190--200, 2005. Google ScholarDigital Library
- P. Magnusson, A. Landin, and E. Hagersten. Queue locks on cache coherent multiprocessors. pages 165--171. Google ScholarDigital Library
- J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on Supercomputing, pages 24--33, New York, NY, USA, 1991. ACM. Google ScholarDigital Library
- J.M. Mellor-Crummey and M.L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst., 9(1):21--65, 1991. Google ScholarDigital Library
- S. Narayanasamy, C. Pereira, and B. Calder. Recording shared memory dependencies using strata. In ASPLOS-XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, pages 229--240, New York, NY, USA, 2006. ACM Press. Google ScholarDigital Library
- S. Narayanasamy, G. Pokam, and B. Calder. Bugnet: Continuously recording program execution for deterministic replay debugging. In ISCA '05: Proceedings of the 32nd annual international symposium on Computer Architecture, pages 284--295, Washington, DC, USA, 2005. IEEE Computer Society. Google ScholarDigital Library
- S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically classifying benign and harmful data racesallusing replay analysis. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 22--31, New York, NY, 2007. Google ScholarDigital Library
- N. Nethercote and J. Seward. How to shadow every byte of memory used by a program. In VEE '07: Proceedings of the 3rd international conference on Virtual execution environments, pages 65--74, New York, NY, USA, 2007. ACM Press. Google ScholarDigital Library
- R. H. B. Netzer. Optimal tracing and replay for debugging shared-memory parallel programs. In PADD '93: Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, pages 1--11, New York, NY, USA, 1993. ACM Press. Google ScholarDigital Library
- R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 167--178, New York, NY, USA, 2003. ACM Press. Google ScholarDigital Library
- V. Project. Helgrind, a data race detector. In http://valgrind.org/docs/manual/hg-manual.html, 2003.Google Scholar
- M. Ronsse and K.D. Bosschere. Recplay: a fully integrated practical record/replay system. ACM Trans. Comput. Syst., 17(2):133--152, 1999. Google ScholarDigital Library
- Y. Saito. Jockey: a user-space library for record-replay debugging. In AADEBUG'05: Proceedings of the sixth international symposium on Automated analysis-driven debugging, pages 69--76, New York, NY, USA, 2005. ACM. Google ScholarDigital Library
- A. Sasturkar, R. Agarwal, L. Wang, and S. D. Stoller. Automated type-based analysis of data races and atomicity. In PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 83--94, New York, NY, USA, 2005. ACM Press. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dynamic data race detector for multi-threaded programs. In SOSP '97: Proceedings of the sixteenth ACM symposium on Operating systems principles, pages 27--37, New York, NY, USA, 1997. ACM Press. Google ScholarDigital Library
- C. von Praun and T. R. Gross. Object race detection. In OOPSLA '01: Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, pages 70--82, New York, NY, USA, 2001. ACM. Google ScholarDigital Library
- S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 programs: Characterization and methodological considerations. In Proceedings of the 22th International Symposium on Computer Architecture, pages 24--36, Santa Margherita Ligure, Italy, 1995. Google ScholarDigital Library
- M. Xu, R. Bodik, and M. D. Hill. A flight data recorder for enabling full-system multiprocessor recorder for enabling full-system multiprocessor deterministic replay. In ISCA '03: Proceedings of the 30th annual international symposium on Computer architecture, pages 122--135, New York, NY, USA, 2003. ACM Press. Google ScholarDigital Library
- Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: efficient detection of data race conditions via adaptive tracking. In SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles, pages 221--234, New York, NY, USA, 2005. ACM Press. Google ScholarDigital Library
Index Terms
- Dynamic recognition of synchronization operations for improved data race detection
Recommendations
Dynamic race detection for C++11
POPL '17: Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming LanguagesThe intricate rules for memory ordering and synchronisation associated with the C/C++11 memory model mean that data races can be difficult to eliminate from concurrent programs. Dynamic data race analysis can pinpoint races in large and complex ...
What are race conditions?: Some issues and formalizations
In shared-memory parallel programs that use explicit synchronization, race conditions result when accesses to shared memory are not properly synchronized. Race conditions are often considered to be manifestations of bugs, since their presence can cause ...
Dynamic race detection for C++11
POPL '17The intricate rules for memory ordering and synchronisation associated with the C/C++11 memory model mean that data races can be difficult to eliminate from concurrent programs. Dynamic data race analysis can pinpoint races in large and complex ...
Comments